МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ ДЕРЖАВНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ І Н С Т Р У К Ц І Я до лабораторної роботи N 4 з курсу " Чисельні методи в інформатиці " для студентів базового напрямку 6.08.04 "Комп'ютерні науки" Затверджено на засіданні кафедри "Системи автоматизованого проектування" Протокол N 14 від 03.04.1997 р. Львів 1999 ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ. Інструкція до лабораторної роботи N 4 з дисципліни "Теоретичні основи САПР" для студентів базового напрямку 6.08.04 "Комп'ютерні науки" / Укл. Мотика І.І., Каркульовський В.І., Чура І.І. – Львів: Видавництво ДУ "Львівська політехніка", 1999. – 10 с. Укладачі Мотика І.І., канд. техн. наук, доц. Каркульовський В.І., канд. техн. наук, доц. Чура І.І., канд. техн. наук, доц. Відповідальний за випуск С.П.Ткаченко, канд. техн. наук, доц. Рецензенти Федасюк Д.В., канд. техн. наук, доц. Близнюк М.Б., канд. техн. наук, доц. 1. МЕТА РОБОТИ Мета роботи – ознайомитись із чисельними методами розв'язування систем лінійних алгебраїчних рівнянь та їх практичним застосуванням. 2. ТЕОРЕТИЧНА ЧАСТИНА Методи розв'язування систем лінійних рівнянь можна поділити на два типи: прямі, або точні, та ітераційні. Прямі методи дають можливість дістати розв'язок, виконавши скінченну апріорі відому кількість операцій. Якщо всі проміжні обчислення виконувати точно (без заокруглень), то отримаємо точний розв'язок. Ітераційні методи дають нескінченну послідовність наближених розв'язків, границі яких є розв'язком системи. 2.1. Прямі методи розв'язування систем лінійних алгебраїчних рівнянь Із точних методів розв'язування систем лінійних рівнянь відомий з курсу лінійної алгебри метод Гаусса, реалізація якого за схемою єдиного ділення вимагає виконання n(4n2-3n-4)/6 арифметичних операцій. Розглянемо розв'язування систем лінійних рівнянь методом Гаусса за схемою Халецького, для реалізації якої необхідно n(2n-1) арифметичних операцій. Система лінійних алгебраїчних рівнянь в матричному представленні має вигляд:  EMBED Equation.3 
 (1) Матрицю коефіцієнтів А подаємо у вигляді добутку двох трикутних матриць, тобто: А=СВ. (2) Матриця С – нижня трикутна, В – верхня трикутна, причому діагональні коефіцієнти матриці В дорівнюють одиниці. Підставимо (2) в (1): CBx=d. (3) Позначимо Bx=y і перепишемо (3) у вигляді: Cy=d (4) Розв'язок (4) називається прямим ходом методу Гаусса, розв'язок (3) – зворотним ходом. Отже, першим кроком при розв'язуванні сформульованої задачі є розбиття матриці А на дві трикутні матриці С і В. Коефіцієнти матриць С і В обчислюються послідовно. Спочатку обчислюється перший стовпець матриці С:  EMBED Equation.2 
, тоді обчислюється перший рядок матриці В:  EMBED Equation.2 
 і елемент  EMBED Equation.2 
, після чого – елементи другого стовпця матриці С:  EMBED Equation.2 
 тоді обчислюються елементи другого рядка матриці В:  EMBED Equation.2 
 і елемент:  EMBED Equation.2 
 і т.д. Після того, як будуть обчислені елементи матриць С і В, а також вектор y, знаходять невідомі  EMBED Equation.2 
:  EMBED Equation.2 
  EMBED Equation.2 
. Алгоритм методу Гаусса за схемою Халецького має такий компактний вигляд:  EMBED Equation.2 
  EMBED Equation.2 
  EMBED Equation.2 
  EMBED Equation.2 
  EMBED Equation.2 
 2.2. Ітераційні методи розв'язування систем лінійних алгебраїчних рівнянь 2.2.1. Метод простої ітерації Найпростішим ітераційним методом розв'язування систем лінійних рівнянь ах=d (5) є метод простої ітерації. Система рівнянь (5) перетворюється до виг...